package org.myy.learn.aaa.a_哈希;

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

@Slf4j
public class 最长连续序列 {

    //方案1：将当前作为起点，的最大长度
    public static int solution1(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums){set.add(num);}
        int longestConsecutive = 0;
        for (int num : nums){
            int curLen = 1;
            int curNum = num;
            if (!set.contains(curNum-1)){
                //int next = curNum+1;  //ToDO 必须放在循环里面
                //while (set.contains(curNum++)) //ToDO 不能在这里curNum++[读取、操作、赋值]，而curNum+1是可以的[读取、操作]
                while (set.contains(curNum+1)){
                    curLen++;
                    curNum++;
                }
            }
            longestConsecutive = Math.max(longestConsecutive, curLen);
        }
        return longestConsecutive;
    }

    //方案2：中心扩展，当前位置，往两边走，l--和r++     >>效率更低呀
    public static int solution2(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums){set.add(num);}
        int longestConsecutive = 0;
        List<Integer> visited = new ArrayList<>();
        for (int center : nums){
            if (visited.contains(center)){continue;}//已使用过

            //左扩展
            int left = center - 1;
            while (set.contains(left)){
                visited.add(left);
                left--;
            }
            left++;

            //右扩展
            int right = center + 1;
            while (set.contains(right)){
                visited.add(right);
                right++;
            }
            right--;

            int curLen = right - left + 1;
            longestConsecutive = Math.max(longestConsecutive, curLen);

            visited.add(center);
        }
        return longestConsecutive;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{8,4,7,1,3,2};
        int solution1 = solution1(nums);
        int solution2 = solution2(nums);
        log.info("执行结束, solution1={}",solution1);
        log.info("执行结束, solution2={}",solution2);
    }
}
